package zijie;

import java.util.List;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class MergeKLists_23_28 {
    /**
     * 两两归并排序
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }
        return merge(lists,0,lists.length - 1);
    }

    public ListNode merge(ListNode[] lists,int l,int r){

        if(l == r){
            return lists[l];
        }
        if(l > r){
            return null;
        }
        int mid = (l + r) >> 1;
        ListNode left = merge(lists,l,mid);
        ListNode right = merge(lists,mid + 1,r);
        return mergerTwoList(left,right);

    }

    public ListNode mergerTwoList(ListNode left, ListNode right){
        if(left == null || right == null){
            return left == null ? right : left;
        }
        ListNode mergerList = new ListNode();
        ListNode helper = mergerList;
        while (left != null && right != null){
            if(left.val < right.val){
                helper.next = left;
                left = left.next;
            }else {
                helper.next = right;
                right = right.next;
            }
            helper = helper.next;
        }
        helper.next = left == null ? right : left;
        return mergerList.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
